package com.wj.algorithm.lintcode;

import java.util.Arrays;
import java.util.Comparator;

public class P184 {
    /*
     * @param nums: A list of non negative integers
     * @return: A string
     */
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return "";
        }

        String[] values = new String[nums.length];
        for (int i = 0, len = nums.length; i < len; i++) {
            values[i] = String.valueOf(nums[i]);
        }

        Arrays.sort(values, new Comparator<String>() {

            @Override
            public int compare(String o1, String o2) {
                return compareString(o1, o2) * -1;
            }
        });

        StringBuilder b = new StringBuilder();
        boolean isFirst = true;
        for (String s : values) {
            if (isFirst && s.startsWith("0")) {
                continue;
            }
            isFirst = false;
            b.append(s);
        }
        if (b.length() < 1) {
            return "0";
        }
        return b.toString();
    }
    
    public static int compareString(String a, String b) {
        
        int al = a.length();
        int bl = b.length();
        int i = 0;
        for(int len = Math.min(al, bl); i < len; i ++) {
            int va = a.codePointAt(i);
            int vb = b.codePointAt(i);
            if(vb > va) {
                return -1;
            } else if(va > vb) {
                return 1;
            }
        }
        
        //处理长度不同的情况
        //长度长的一方，下一个字符与短的一方的最后一个字符，比较大小
        if(al > bl) {
            int va = a.codePointAt(i);
            int vb = b.codePointAt(i - 1);
            if(va > vb){
                return 1;
            } else if(vb > va) {
                return -1;
            }
        } else if(bl > al) {
            int va = a.codePointAt(i - 1);
            int vb = b.codePointAt(i);
            if(va > vb){
                return 1;
            } else if(vb > va) {
                return -1;
            }
        }
        
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(new P184().largestNumber(new int[] { 1, 20, 23, 4, 8 }));
        System.out.println(new P184().largestNumber(new int[] { 41, 23, 87, 55, 50, 53, 18, 9, 39, 63, 35, 33, 54, 25, 26, 49, 74, 61, 32, 81, 97, 99, 38, 96,
                22, 95, 35, 57, 80, 80, 16, 22, 17, 13, 89, 11, 75, 98, 57, 81, 69, 8, 10, 85, 13, 49, 66, 94, 80, 25, 13, 85, 55, 12, 87, 50, 28, 96, 80, 43,
                10, 24, 88, 52, 16, 92, 61, 28, 26, 78, 28, 28, 16, 1, 56, 31, 47, 85, 27, 30, 85, 2, 30, 51, 84, 50, 3, 14, 97, 9, 91, 90, 63, 90, 92, 89, 76,
                76, 67, 55 }));

        System.out.println(compareString("98", "9"));
        System.out.println(compareString("1234", "5"));
        System.out.println(compareString("43", "42"));
        System.out.println(compareString("21", "2"));
    }
}
